The present invention is directed to an apparatus for decoding variable length instantaneous codes. Binary codes are used in present day data processing systems for representing normal data processing information such as alphanumeric characters, computer instructions, messages and various graphic entities. These codes are usually of fixed-length due to the fixed size of the storage elements in computer memories and the simplicity of implementing fixed-length decoders. It has been recognized that the use of variable-length code words provides a more efficient representation (fewer binary digits) than fixed-length code words, especially when the code words have a skewed probability distribution. This is especially the case in digital data processing where the use of bit addressable memory systems utilized in conjunction with variable-length code words can greatly reduce the amount of memory required for the processing system.
The decoding of variable-length code words residing in memory is not trivial, since in giving a coded message it is necessary to determine where the first code word ends and the next code word begins. This type of code is generally referred to as an instantaneous code wherein it is possible to decode each code word in a sequence without reference to succeeding code symbols. Inherent in instantaneous codes is the requirement that no complete word of the code be a prefix of some other code word. Example of such a code is the minimum-redundancy code described in D. A. Huffman "A Method for the Construction of Minimum-Redundancy Codes" Proceedings of IRE, Volume 40, Pp. 1098-1101, September, 1952. Prior decoding circuits for decoding Huffman type codes have usually used a tree searching technique, an example which can be found in U.S. Pat. No. 3,918,047, issued Nov. 4, 1975, to P. B. Denes which requires a number of logic circuit modules to be interconnected in a pattern corresponding to a tree representation of the code. The speed of such a decoding circuit has been found to be limited due to the number of gate delays found in such a circuit. In U.S. Pat. No. 3,701,108, issued Oct. 24, 1972 to Loh et al., a processor for encoding and decoding variable-length dependent code words is disclosed in which the fixed-length code words are assigned to a coding set based on the probability of each word occurring after a preceding word, which coding set is used in encoding and decoding the variable-length code words. This type of processing requires large memories which add to the cost of the processing system. It is therefore an object of this invention to provide a unique representation of a parallel decoder for decoding an instantaneous variable-length code. It is a further object of this invention to provide a decoder whose decoding time is significantly faster than the decoders found in the current state of the art and which is of simple construction and therefore low in cost.